package com.cheng.algorithm.huffmancode;

import java.util.*;

/**
 * @User Administrator
 * @Classname HuffmanCode
 * @Project Data-structure-and-algorithm
 * @Description 赫夫曼编码代码实现：
 * 赫夫曼编码基本介绍：
 * 1)赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式,属于一种程序算法
 * 2)赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
 * 3)赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%~90%之间
 * 4)赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码
 * 通信领域中信息的处理方式-赫夫曼编码原理剖析：
 * 要进行编码的字符串为：【i like like like java do you like a java】，共40个字符(包括空格)
 * 统计各个字符对应的个数：d:1 y:1 u:1 j:2 v:2 o:2l:4 k:4 e:4 i:5 a:5  :9
 * 按照上面字符出现的次数构建一颗赫夫曼树，次数作为节点的权值
 * 根据构建好的赫夫曼树，节点向左的路径为0，向右的路径为1，则各个字符的赫夫曼编码如下：
 * a:110 k:1110 e:1111 j:0000 v:0001 l:001  :01(空格)
 * 根据上面各个字符的赫夫曼编码，字符串：【i like like like java do you like a java】对应的赫夫曼编码为：
 * 10101001101111011110100110111101111010011011110111101000011000011100110011110000110111000100100100110111101111011100100001100001110
 * 关于赫夫曼编码说明：
 * 1)赫夫曼编码使用的是无损压缩
 * 2)此编码满足前缀编码，即字符的编码都不能是其他亨符编码的前缀。不会造成匹配的多义性
 * 3)赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是wpl是一样的，都是最小的,比如:如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个
 *
 *
 * @Author wpcheng
 * @Create 2021-09-02-11:38
 * @Version 1.0
 */
public class HuffmanCode {
    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        //将String编码为字节序列，并将结果存储到新的字节数组中。
        byte[] contentBytes = content.getBytes();
        //调用封装后的赫夫曼编码方法
        byte[] huffmanByteCodes = huffmanZip(contentBytes);
        System.out.println("赫夫曼编码转成byte[]为："+Arrays.toString(huffmanByteCodes));

        //测试赫夫曼解码后，输出原始字符串
        byte[] bytes = decode(huffmanCodes, huffmanByteCodes);
        System.out.println(new String(bytes)); // i like like like java do you like a java


        /*
        System.out.println(contentBytes.length);//40
        List<Node> nodeList = getNode(contentBytes);
        System.out.println("nodeList="+nodeList);
        // nodeList=[  字符用ASCII码来表示，如 32=' ', 97='a', 100='d'......
        // Node{data=32, weight=9}, Node{data=97, weight=5}, Node{data=100, weight=1}, Node{data=101, weight=4},
        // Node{data=117, weight=1},Node{data=118, weight=2}, Node{data=105, weight=5}, Node{data=121, weight=1},
        // Node{data=106, weight=2},Node{data=107, weight=4}, Node{data=108, weight=4}, Node{data=111, weight=2}
        // ]

        //构造赫夫曼树，返回赫夫曼树的根节点
        Node node = createHuffmanTree(nodeList);

        //赫夫曼树前序遍历输出
        preOrder(node);

        //测试生成的赫夫曼编码表
        getCodes(node);
        System.out.println(huffmanCodes);
        //{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}

        //测试4.2：将4.1得到的字符串对应的赫夫曼编码字符转成byte[]
        byte[] huffmanByteCodes = huffmanZip(contentBytes, huffmanCodes);
        System.out.println("赫夫曼编码转成byte[]为："+Arrays.toString(huffmanByteCodes));
        //[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] 长度：17，压缩率57.5%
        */
    }

    /*对赫夫曼编码后的byte[]进行解码，得到原始字符串，赫夫曼解码实质就是赫夫曼编码的逆向过程
    *  解码思路：
    * 第1步.先将huffmanByteCodes转成赫夫曼编码对应的二进制字符串
    * [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] --->
    * 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
    * 第2步、将赫夫曼编码对应的二进制字符串转成原始字符串
    * 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100 --->
    * i like like like java do you like a java
    */

    /**
     * 将huffmanByteCodes字节数组中的数转成赫夫曼编码对应的二进制字符串
     * @param flag 标志位，判断是否需要补高位，为true，表示需要补高位,如果是数组最后一个字节，无需补高位
     * @param b  huffmanByteCodes字节数组
     * @return  字节数组对应的赫夫曼编码二进制字符串，按补码返回，在编码时，根据赫夫曼编码表得到的赫夫曼编码二进制字符串也是补码的形式
     */
    private static String byteToBitString(boolean flag,byte b){
        //将b转换成int类型
        int temp = b;

        if (flag){
            temp |= 256; //按位与256，256二进制为 1 0000 0000，假设temp为1，1 0000 0000 | 0000 0001 = 1 0000 0001
        }
        String str = Integer.toBinaryString(temp);//返回temp对应的二进制补码
        if (flag){
            return str.substring(str.length() - 8);//截取最后八位字符
        }else {
            return str;
        }
    }


    /**
     *
     * @param huffmanCodes 原始字符串对应的赫夫曼编码表 a:110 k:1110 e:1111 j:0000 v:0001 l:001  :01(空格)
     * @param huffmanCodeBytes 赫夫曼编码处理后的byte[]  [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
     * @return 返回原始字符串转换成的byte[]
     */
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanCodeBytes){
        //把赫夫曼编码处理后的byte[]转换成二进制的赫夫曼编码
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanCodeBytes.length; i++) {
            byte b = huffmanCodeBytes[i];//取出字节数组中的字节
            //判断是不是最后一个字节,如果是，flag=true，就不用补高位
            boolean flag = (i == huffmanCodeBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag,b));
        }
        //把二进制的赫夫曼编码转换成原始字符串
        //把赫夫曼编码表调换，因为要逆向查询，a:97-->97:a
        Map<String,Byte> map = new HashMap<String,Byte>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(),entry.getKey());//逆向存储到map集合中
        }
        //创建一个集合，存放原始字符串字节数组
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length();) {
            int count = 1;
            boolean flag = true;
            Byte b = null;

            while (flag){
                //对stringBuilder进行扫描
                String key = stringBuilder.substring(i , i+count);
                b = map.get(key);//看扫描到的字符串是否和map中的匹配
                //如果匹配不到，继续扫描
                if (b == null){
                    count++;
                }else {//如果匹配到
                    flag = false;
                }
            }
            list.add(b);//把扫描到的字符放入集合
            i += count; //i移动到count的位置上，继续扫描
        }
        byte[] b = new byte[list.size()];
        //把链表中的字符放入数组
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }


    /**
     *  封装赫夫曼编码的方法，方便调用
     * @param bytes 原始字符串对应的字节数组contentBytes
     * @return 返回经过赫夫曼编码处理后的字节数组
     */
    private static byte[] huffmanZip(byte[] bytes){
        //1、将原始字节数组转成node形式的数组
        List<Node> nodeList = getNode(bytes);
        //2、根据node节点数组构造赫夫曼树，并返回赫夫曼树的根节点
        Node node = createHuffmanTree(nodeList);
        //3、得到赫夫曼树对应的赫夫曼编码表
        Map<Byte, String> huffmanCodes = getCodes(node);
        //4、先根据赫夫曼编码表得到原始字符串对应赫夫曼编码数据，再把原始字符串对应赫夫曼编码数据压缩成byte[]
        byte[] huffmanByteCodes = huffmanZip(bytes, huffmanCodes);
        return huffmanByteCodes;
    }



    //前序遍历
    private static void preOrder(Node root){
        if (root != null){
            root.preOrder();
        }else {
            System.out.println("赫夫曼树为空");
        }
    }

    //重载getCodes
    private static Map<Byte,String> getCodes(Node root){
        if (root == null){
            System.out.println("节点为空"); ;
        }else {
            getCodes(root.left,"0",stringBuilder);
            getCodes(root.right,"1",stringBuilder);

        }
        return huffmanCodes;

    }

    /**
     *  1、将字节数组转成node形式的数组
     * @param bytes   字节数组
     * @return 返回node数组
     */
    private static List<Node> getNode(byte[] bytes){
        //1、创建一个ArrayList
        ArrayList<Node> nodes = new ArrayList<Node>();

        //遍历bytes，统计每一个字符出现的次数
        HashMap<Byte, Integer> counts = new HashMap<>();//用map存储每一个字符出现了多少次，key为字符Byte，value为出现的次数Integer
        for (byte b : bytes) {
            Integer count = counts.get(b);//设置k-v键值对
            //如果当前count为空，说明该字符第一次被遍历
            if (count == null){
                counts.put(b,1);
            //如果不为空，就在之前出现的次数上+1
            }else {
                counts.put(b,count + 1);
            }
        }
        //遍历map，将map集合里的每一个键值对转成Node对象，并加入nodes集合中
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) { //entrySet()，返回map中各个键值对映射关系的集合，使用它对map进行遍历
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }

        return nodes;
    }

    //2、构造对应的赫夫曼树
    private static Node createHuffmanTree(List<Node> nodes) {

        while (nodes.size() > 1){
            //对node链表中的节点从小到大进行排序
            Collections.sort(nodes);
            //取出最小的二叉树（每个节点可以看成是—颗最简单的二叉树）
            Node leftNode = nodes.get(0);
            //取出次小的二叉树
            Node rightNode = nodes.get(1);
            //组成─颗新的二叉树,该新的二叉树根节点没有data，只有权值
            Node parent = new Node(null,leftNode.weight + rightNode.weight);
            //新二叉树的左右节点
            parent.left = leftNode;
            parent.right = rightNode;

            //在node链表中删除掉使用过得节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将新的树的权值放入node链表
            nodes.add(parent);
        }
        //返回赫夫曼书的根节点
        return nodes.get(0);
    }


    //将赫夫曼编码存放在map集合中，形式如 97:110
    static Map<Byte,String> huffmanCodes =  new HashMap<Byte,String>();
    //字符对应的赫夫曼编码需要拼接路径，定义StringBuilder存储编码路径
    static StringBuilder stringBuilder = new StringBuilder();
    /**
     * 3、得到赫夫曼树对应的赫夫曼编码表，如：a:110 k:1110 e:1111 j:0000 v:0001 l:001  :01，这里的字符待会还是用ASCII表示
     * @param node 遍历的节点，从根节点开始
     * @param code 节点路径，左子节点的路径为0，右子节点的路径为1
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        //节点不为空
        if (node != null){
            //node.data == null，说明该节点是非叶子节点
            if (node.data == null){
                //进行递归
                getCodes(node.left,"0",stringBuilder2);//向左递归
                getCodes(node.right,"1",stringBuilder2);//向右递归
            //如果该节点是叶子结点，就放入map
            }else {
                huffmanCodes.put(node.data,stringBuilder2.toString());
            }
        }
    }



    /**
     * 4、使用赫夫曼编码来生成对应字符串的赫夫曼编码数据 ,即按照上面的赫夫曼编码，将"i like like like java do you like a java”字符串生成对应的编码数据,再压缩成byte[]
     * @param bytes 原始字符串对应的字节数组  contentBytes
     * @param huffmanCodes 字节数组对应的赫夫曼编码表 ，如下：
     * {32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
     * 4.1、先返回赫夫曼编码处理好的二进制数据，如下：
     * 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
     * 4.2、再将赫夫曼编码数据压缩成8位一个的byte数组，如下：
     * 前八位，huffmanCodeBytes[0] = 10101000(补码，符号位为1，是负数) -->10100111（反码）-->11011000（原码），先把前八位转成原码，该原码对应的byte数为 -88
     *
     */
    private static byte[] huffmanZip(byte[] bytes,Map<Byte,String> huffmanCodes){
        //4.1、先返回赫夫曼编码处理好的数据
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        //测试4.1、根据赫夫曼编码表返回字符串对应的赫夫曼编码
        //System.out.println("测试生成的赫夫曼编码数据："+stringBuilder.toString());
        //4.2、将赫夫曼编码数据压缩成8位一个的byte数组
        int len; //统计压缩后byte[]的长度
        int index = 0; //定义byte[]下标
        if (stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;
        }else {
            len = stringBuilder.length() / 8 + 1;
        }
        //创建byte[] huffmanByteCodes,长度为len
        byte[] huffmanByteCodes = new byte[len];
        for (int i = 0; i < stringBuilder.length(); i+=8) {
            String strByte;
            //如果 stringBuilder.length()不够八位，就从第一个位置开始，截取全部
            if (i + 8 > stringBuilder.length()){
                strByte = stringBuilder.substring(i);
            }else {
                strByte = stringBuilder.substring(i,i+8);//每八位截取一次，放入strByte
            }
            //将strByte按二进制转成byte[]
            huffmanByteCodes[index] = (byte) Integer.parseInt(strByte,2);
            index++;
        }
        return huffmanByteCodes;
    }
}

class Node implements Comparable<Node>{
    Byte data;//存放数据
    int weight;//节点权值，就是字符出现的次数
    Node left;
    Node right;

    public Node(Byte data,int weight){
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        //从小到大
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
    //前序遍历
    public void preOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.preOrder();
        }
        if (this.right != null){
            this.right.preOrder();
        }
    }
}